#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> dx={0,0,1,-1};
    vector<int> dy={1,-1,0,0};
    typedef tuple<int,int,int> tiii;
    const int INF=0x3f3f3f3f;
    int minimumEffortPath(vector<vector<int>>& heights) {
        int n=heights.size();
        int m=heights[0].size();
        vector<vector<int>> d(n,vector<int>(m,INF));
        priority_queue<tiii,vector<tiii>,greater<>> q;
        q.emplace(0,0,0);
        d[0][0]=0;
        while(!q.empty())
        {
            auto [d_x,x,y]=q.top();
            q.pop();
            if(d_x>d[x][y]) continue;
            for(int i=0;i<4;i++)
            {
                int cx=x+dx[i];
                int cy=y+dy[i];
                if(cx>=0&&cy>=0&&cx<n&&cy<m)
                {     
                    int k=max(d[x][y],abs(heights[cx][cy]-heights[x][y]));
                    if(d[cx][cy]>k)
                    {
                        d[cx][cy]=k;
                        q.emplace(d[cx][cy],cx,cy);
                    }
                }
            }
        }
        return d[n-1][m-1];
    }
};